package 中等.搜索.回溯;

import java.util.Arrays;

/**
 * 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个
 * 火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任
 * 何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
 * 如果你能使这个正方形，则返回 true ，否则返回 false 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/matchsticks-to-square
 */
public class 火柴拼正方形_473 {

    public static void main(String[] args) {

        int[] nums = {2, 2, 2, 1, 1};
        System.out.println(new 火柴拼正方形_473().makesquare(nums));

    }

    /**
     * 回溯+剪枝
     * 相当于遍历每一种情况
     * 遍历思路:
     * bucket[i] 表示索引 i 所在的边的剩余长度，遍历 matchsticks[j]
     * 将第 1 根火柴 尝试 放到 bucket[i] 中，如果可以放入其中一条边，
     * 那么将剩余长度更新 bucket[i] -= matchsticks[0]
     * 那么将第 2 根火柴 尝试 放到 bucket[i] 中，如果遍历到最后，没有
     * 一条边可以放下第 2 根火柴，那么说明第 1 根火柴放错位置了，将
     * bucket[i]回溯到没有放入第 1 根火柴的状态，即 bucket[i] += matchsticks[0]
     *
     * @param matchsticks
     * @return
     */
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int matchstick : matchsticks) {
            sum += matchstick;
        }
        if (sum % 4 != 0) return false;

        // 优先放置长度较长的火柴，使得更容易失败
        Arrays.sort(matchsticks);
        if (matchsticks[matchsticks.length - 1] > sum / 4) return false;

        // 可以从0开始装，装到 sum/4
        int[] buckets = new int[4];
        Arrays.fill(buckets, sum / 4);
        // 自定义降序排序，需要引用类型
        // 逆序思维，这里直接倒序遍历
        return dfs(matchsticks.length - 1, buckets, matchsticks);
    }

    // index 为火柴的索引，如果能放下，那么 index+1，否则，
    // 将 index 的火柴，尝试放到下一条边
    // 将 index 的火柴，在四条边都尝试过，失败之后
    // 说明不能拼成正方形
    // 如果 index = -1，说明火柴硬件全部放完
    private boolean dfs(int index, int[] buckets, int[] matchsticks) {
        if (index == -1) return true;
        for (int i = 0; i < buckets.length; i++) {
            // 剪枝
            // 1，如果当前边不能放入当前火柴，条件当前边
            // 2，如果当前边的容量和前面的边是一致的，那么前面的边不能够完全放入，那么当前边也不行
            // 3，这里不需要遍历前面全部的边
            if (buckets[i] - matchsticks[index] < 0 || (i > 0 && buckets[i] == buckets[i - 1])) {
                continue;
            }

            buckets[i] -= matchsticks[index];
            // 下一个火柴是否可以放置
            if (dfs(index - 1, buckets, matchsticks)) {
                return true;
            }
            buckets[i] += matchsticks[index];
        }
        return false;
    }

}

